/*
 * @lc app=leetcode.cn id=567 lang=typescript
 *
 * [567] 字符串的排列
 */

// @lc code=start

//  思路：双指针
//  窗口缩小的时机是窗口大小大于s1.length时
//  valid == need.size() 时，就说明窗口中就是一个合法的排列
//  参考：https://labuladong.github.io/algo/2/19/51/

//  复杂度：O(n) O(n)

function checkInclusion(s1: string, s2: string): boolean {
    const need: Map<string, number> = new Map()
    const window: Map<string, number> = new Map()
    for (const c of s1) {
        need.set(c, need.has(c) ? need.get(c)! + 1 : 1)
    }

    let left = 0, right = 0, valid = 0
    while (right < s2.length) {
        const c = s2[right]
        right++
        // 进行窗口内数据的一系列更新
        if (need.has(c)) {
            window.set(c, window.has(c) ? window.get(c)! + 1 : 1)
            if (window.get(c) === need.get(c)) {
                valid++
            }
        }

        // 判断左侧窗口是否要收缩
        while (right - left >= s1.length) {
            // 在这里判断是否找到了合法的子串
            if (valid === need.size) {
                return true
            }
            const d = s2[left]
            left++
            // 进行窗口内数据的一系列更新
            if (need.has(d)) {
                if (window.get(d) === need.get(d)) {
                    valid--
                }
                window.set(d, window.get(d)! - 1)
            }
        }
    }
    return false
};
// @lc code=end


console.log(checkInclusion('ab', 'eidbaooo'))  // true
console.log(checkInclusion('ab', 'eidboaoo'))  // false
